package algorithms.a07graphBasics;

import com.google.common.base.Preconditions;

import java.util.Iterator;

/**
 * 联通分量
 * 通过一个图来构造，通过深度优先遍历获取联通分量的个数
 * @author 王昊然
 * @create 2018-03-02 10:51
 **/
public class Components {

    private Graph graph;
    private int ccount = 0;//连通分量的个数
    private boolean isVisited[];//存储节点是否遍历过
    private int ids[]; //用来存储两点间是否能连接的信息（并查集）

    public Components(Graph graph){
        this.graph = graph;
        this.isVisited = new boolean[graph.V()];//初始化，默认都是false
        this.ids = new int[graph.V()];

        for (int i = 0; i < graph.V(); i++) {
            if(!isVisited[i]){
                dfs(i);
                ccount ++;
            }
            ids[i] = ccount;
        }
    }

    private void dfs(int v) {
        isVisited[v] = true;
        Iterator<Integer> iterator = graph.adj(v).iterator();
        while (iterator.hasNext()){
            Integer next = iterator.next();
            if(isVisited[next] == false){
                dfs(next);
            }
        }
    }

    public int count(){
        return ccount;
    }

    public boolean isConnected(int v, int w){
        Preconditions.checkArgument(v<graph.V() && w<graph.V(), "参数超出范围");
        return ids[v] == ids[w];
    }


    public static void main(String[] args) {

        // TestG1.txt
        String filename1 = "testG1.txt";
        SparseGraph g1 = new SparseGraph(13, false);
        ReadGraph readGraph1 = new ReadGraph(g1, filename1);
        Components component1 = new Components(g1);
        System.out.println("TestG1.txt, Component Count: " + component1.count());
        System.out.println();

        // TestG2.txt
        String filename2 = "testG2.txt";
        SparseGraph g2 = new SparseGraph(6, false);
        ReadGraph readGraph2 = new ReadGraph(g2, filename2);
        Components component2 = new Components(g2);
        System.out.println("TestG2.txt, Component Count: " + component2.count());
    }
}
